{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Impossible OR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #brainteaser #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #脑筋急转弯 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minImpossibleOR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小无法得到的或值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果存在一些整数满足&nbsp;<code>0 &lt;= index<sub>1</sub> &lt; index<sub>2</sub> &lt; ... &lt; index<sub>k</sub> &lt; nums.length</code>&nbsp;，得到&nbsp;<code>nums[index<sub>1</sub>] | nums[index<sub>2</sub>] | ... | nums[index<sub>k</sub>] = x</code>&nbsp;，那么我们说&nbsp;<code>x</code>&nbsp;是&nbsp;<strong>可表达的</strong>&nbsp;。换言之，如果一个整数能由&nbsp;<code>nums</code>&nbsp;的某个子序列的或运算得到，那么它就是可表达的。</p>\n",
    "\n",
    "<p>请你返回 <code>nums</code>&nbsp;不可表达的 <strong>最小非零整数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,1]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>1 和 2 已经在数组中，因为 nums[0] | nums[1] = 2 | 1 = 3 ，所以 3 是可表达的。由于 4 是不可表达的，所以我们返回 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [5,3,2]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>1 是最小不可表达的数字。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-impossible-or](https://leetcode.cn/problems/minimum-impossible-or/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-impossible-or](https://leetcode.cn/problems/minimum-impossible-or/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1]', '[5,3,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        mask = 0\n",
    "        for x in nums:\n",
    "            if x & (x-1) == 0:\n",
    "                mask |= x\n",
    "        mask = ~mask\n",
    "        return mask & (-mask)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        bits = [inf] * 32\n",
    "        for x in nums:\n",
    "            for i in range(32):\n",
    "                if x & (1 << i) > 0:\n",
    "                    bits[i] = min(bits[i], x)\n",
    "        for i in range(32):\n",
    "            if (1 << i) < bits[i]:\n",
    "                return 1 << i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        res = 1\n",
    "        while res in nums: res <<= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        for i in range(n+1):\n",
    "            if 2**i not in nums:\n",
    "                return 2**i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        mask = 0\n",
    "        for x in nums:\n",
    "            if (x & (x - 1)) == 0:\n",
    "                mask |= x\n",
    "        mask = ~mask\n",
    "        return mask & -mask"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        将二进制数写出来可以发现，由于是或运算，那些末尾全为0的数很重要，即2的幂次的数：1、2、4、8...\n",
    "        1、2可以通过或运算得到3；1、2、4可以通过或运算得到5、6、7；对后面的也是同理\n",
    "        因此，只需要关注数组nums中缺少的最小的2的幂次，记为x，该幂次是无法通过其他数的或运算进行表达的。\n",
    "        即2的0次方到2的x次方-1都可以被表达， 但2的x次方无法被表达。\n",
    "        '''\n",
    "\n",
    "        '''\n",
    "        进一步优化，由于只需要看2的幂次，可以用一个mask记录nums中是2的幂次的数。\n",
    "        答案是mask中的最低比特0。这可以通过对mask取反后，用lowbit得到。\n",
    "        举个例子，对nums进行扫描后记录所有2的幂次，得到mask，假设为110001100111，我们关心的是最低位的0。\n",
    "        ~是按位取反操作，包括符号位，对于正数而言，先各位取反变为复数，显示是再转化为其补码。\n",
    "        如上述mask加上符号位表示为0110001100111，先按位取反得到1001110011000，再转化为补码(除符号位外各位取反再加1)得到1110001101000。\n",
    "        这时再用x & (-x)求lowbit，得到第四位的1，即为我们最初关心的最低位的0。\n",
    "        '''\n",
    "        mask = 0\n",
    "        for x in nums:\n",
    "            if (x & (x - 1)) == 0:  # x 是 2 的幂次\n",
    "                mask |= x           # 记录所有 2 的幂次\n",
    "        mask = ~mask                # 按位取反\n",
    "        return mask & -mask         # lowbit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        for i in range(31):\n",
    "            if (1<<i) not in nums:\n",
    "                return 1<<i\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        将二进制数写出来可以发现，由于是或运算，那些末尾全为0的数很重要，即2的幂次的数：1、2、4、8...\n",
    "        1、2可以通过或运算得到3；1、2、4可以通过或运算得到5、6、7；对后面的也是同理\n",
    "        因此，只需要关注数组nums中缺少的最小的2的幂次，记为x，该幂次是无法通过其他数的或运算进行表达的。\n",
    "        即2的0次方到2的x次方-1都可以被表达， 但2的x次方无法被表达。\n",
    "        '''\n",
    "        nums.sort()\n",
    "        x = 0\n",
    "        for num in nums:\n",
    "            if num == (1 << x):             #num == 2的x次方\n",
    "                x += 1\n",
    "            elif num > (1 << x):            #找到缺少的2的幂次\n",
    "                break\n",
    "        return 1 << x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        m = 0\n",
    "        for x in nums:\n",
    "            if x & (x - 1) == 0:\n",
    "                m |= x\n",
    "        m = ~m\n",
    "        return m & -m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        mask = 0\n",
    "\n",
    "        for num in nums:\n",
    "            if num & (num -1) == 0:\n",
    "                mask |= num\n",
    "            \n",
    "        mask = ~mask\n",
    "        # lowbit   \n",
    "        return mask & -mask"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minImpossibleOR(self, nums):\n",
    "        ans=0\n",
    "        while 1:\n",
    "            if 2**ans not in nums:\n",
    "                return 2**ans\n",
    "            ans+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        mask = 0\n",
    "        for x in nums:\n",
    "            if (x & (x - 1)) == 0:  # x 是 2 的幂次\n",
    "                mask |= x\n",
    "        mask = ~mask\n",
    "        return mask & -mask  # lowbit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "    \n",
    "        # 10 | 01 => 1 2 3\n",
    "        # 100 |010 | 001 => 5 6 7 \n",
    "        nums.sort()\n",
    "        if nums[0] > 1:\n",
    "            return 1\n",
    "\n",
    "        i = 1\n",
    "        o = 0\n",
    "        for j, v in enumerate(nums):\n",
    "            o |= v\n",
    "\n",
    "            if v < i:\n",
    "                continue\n",
    "\n",
    "            if i != v or i & o == 0:\n",
    "                return i\n",
    "            \n",
    "            while i <= o:\n",
    "                i <<= 1\n",
    "\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        mask = 0\n",
    "        for x in nums:\n",
    "            if (x & (x - 1)) == 0:\n",
    "                mask |= x\n",
    "        mask = ~mask\n",
    "        return mask & -mask"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        mask = 0\n",
    "        for x in nums:\n",
    "            if (x & (x - 1)) == 0:  # x 是 2 的幂次\n",
    "                mask |= x\n",
    "        mask = ~mask\n",
    "        return mask & -mask  # lowbit\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minImpossibleOR(self, nums):\n",
    "        ans=0\n",
    "        while 1:\n",
    "            if 2**ans not in nums:\n",
    "                return 2**ans\n",
    "            ans+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        mask = 0\n",
    "        for x in nums:\n",
    "            if (x & (x - 1)) == 0:  # x 是 2 的幂次\n",
    "                mask |= x\n",
    "        mask = ~mask\n",
    "        return mask & -mask  # lowbit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        mask = 0\n",
    "        for x in nums:\n",
    "            if (x & (x - 1)) == 0:  # x 是 2 的幂次\n",
    "                mask |= x\n",
    "        mask = ~mask\n",
    "        return mask & -mask  # 返回最低位\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        # 方法一\n",
    "        # s = set(nums)\n",
    "        # for i in range(32):\n",
    "        #     if 1 << i not in s:\n",
    "        #         return 1 << i\n",
    "\n",
    "        # 方法二\n",
    "        mask = 0\n",
    "        for x in nums:\n",
    "            if (x & (x - 1)) == 0:  # x 是 2 的幂次\n",
    "                mask |= x\n",
    "        mask = ~mask\n",
    "\n",
    "        return mask & -mask         # lowbit\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minImpossibleOR(self, nums):\n",
    "        for x in [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824]:\n",
    "            if x not in nums: return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        sum_or = 0\n",
    "        cnt = Counter()\n",
    "        for x in nums:\n",
    "            if x.bit_count() == 1:\n",
    "                m = x.bit_length() - 1\n",
    "                cnt[m] += 1\n",
    "        i = 0\n",
    "        while True:\n",
    "            if cnt[i] == 0:\n",
    "                return 2 ** i\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minImpossibleOR(self, nums):\n",
    "        ans=0\n",
    "        while 1:\n",
    "            if 2**ans not in nums:\n",
    "                return 2**ans\n",
    "            ans+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minImpossibleOR(self, nums):\n",
    "        for x in [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824]:\n",
    "            if x not in nums: return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        inf = float('inf')\n",
    "        bitMins = defaultdict(lambda: inf)\n",
    "        for n in nums:\n",
    "            nn = n\n",
    "            while nn:\n",
    "                bit = nn & -nn\n",
    "                bitMins[bit] = min(bitMins[bit], n)\n",
    "                nn -= bit\n",
    "        bit = 1\n",
    "        while True:\n",
    "            _min = bitMins[bit]\n",
    "            if _min != bit: return bit\n",
    "            bit <<= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        i = 0\n",
    "        s = set(nums)\n",
    "        while True:\n",
    "            if 1 << i not in s:\n",
    "                return 1 << i\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        return next(1 << i for i in count() if 1 << i not in s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        for i in range(31):\n",
    "            if 1 << i not in s:\n",
    "                return 1 << i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        vis = set(nums)\n",
    "        for i in range(31):\n",
    "            x = 1 << i\n",
    "            if x not in vis:\n",
    "                return x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        return next(1<<i for i in count() if 1<<i not in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        将二进制数写出来可以发现，由于是或运算，那些末尾全为0的数很重要，即2的幂次的数：1、2、4、8...\n",
    "        1、2可以通过或运算得到3；1、2、4可以通过或运算得到5、6、7；对后面的也是同理\n",
    "        因此，只需要关注数组nums中缺少的最小的2的幂次，记为x，该幂次是无法通过其他数的或运算进行表达的。\n",
    "        即2的0次方到2的x次方-1都可以被表达， 但2的x次方无法被表达。\n",
    "        '''\n",
    "        s = set(nums)\n",
    "        return next(1 << i for i in count() if 1 << i not in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s=set(nums)\n",
    "        for i in range(31):\n",
    "            if 1<<i not in s:\n",
    "                return 1<<i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        i = 0\n",
    "        while True:\n",
    "            if 2**i not in s:\n",
    "                return 2**i\n",
    "            i += 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s=set(nums)\n",
    "        for i in range(31):\n",
    "            if 1<<i not in s:\n",
    "                return 1<<i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        tmp = set(nums)\n",
    "        ans = 1\n",
    "        while ans in tmp:\n",
    "            ans *= 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        for i in range(33):\n",
    "            if 1<<i not in s: return 1<<i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        \n",
    "        dct = set(nums)\n",
    "        for i in range(34):\n",
    "            if 1<<i not in dct:\n",
    "                return 1<<i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\r\n",
    "        st = set(nums)\r\n",
    "        return next(1 << i for i in count() if 1 << i not in st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        for i in range(len(nums) + 1):\n",
    "            tmp = 2 ** i\n",
    "            if tmp not in s:\n",
    "                return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        tmp = set(nums)\n",
    "        ans = 1\n",
    "        while ans in tmp:\n",
    "            ans *= 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        #copy 0x3\n",
    "        s = set(nums)\n",
    "        return next(1<<i for i in count() if 1<<i not in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        ans = 1\n",
    "        while ans in nums:\n",
    "            ans <<= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        for i in range(32):\n",
    "            if 2 ** i not in s:\n",
    "                return 2 ** i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\r\n",
    "        s = set(nums)\r\n",
    "        return next(1 << i for i in count() if 1 << i not in s)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, a: List[int]) -> int:\n",
    "        s=set(a)\n",
    "        i=1\n",
    "        while i in s:\n",
    "            i*=2\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        return next(1 << i for i in count() if 1 << i not in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        tmp = set(nums)\n",
    "        ans = 1\n",
    "        while ans in tmp:\n",
    "            ans *= 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        return next(1 << i for i in count() if 1 << i not in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        tmp = set(nums)\n",
    "        ans = 1\n",
    "        while ans in tmp:\n",
    "            ans *= 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        i=0\n",
    "        nums=set(nums)\n",
    "        while True: \n",
    "            if 1<<i not in nums:\n",
    "                return 1<<i\n",
    "            i+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        for i in range(32):\n",
    "            if 1<<i not in s:\n",
    "                return 1<<i\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minImpossibleOR(self, nums: List[int]) -> int:\n",
    "        # 方法一\n",
    "        s = set(nums)\n",
    "        for i in range(32):\n",
    "            if 1 << i not in s:\n",
    "                return 1 << i\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
